n=1000;
a=9211;
b=6189;
minister=[|3297,589|
9975,8466|
80,341|
779,1883|
8314,39|
60,7691|
9107,6172|
4178,8589|
9747,865|
5064,4430|
1257,8928|
5346,1132|
8678,602|
5938,1790|
4943,9367|
4993,1502|
1742,5632|
401,2743|
2273,8078|
5765,5621|
3603,1646|
1304,7319|
7256,5621|
9826,9787|
2048,9437|
7352,8934|
6807,8611|
5044,8634|
9411,3581|
241,3277|
3697,2414|
8085,9316|
5581,7341|
6675,5755|
837,2185|
8924,8939|
4351,1156|
8658,9725|
8838,9643|
847,8351|
2156,2122|
509,2313|
5416,8356|
8735,104|
421,4947|
5529,803|
20,5881|
9335,532|
1522,3770|
5834,2290|
81,4041|
3883,929|
5998,5540|
1902,6073|
1997,9353|
3241,9214|
8804,7607|
6269,6883|
9520,3513|
1869,9519|
4676,8412|
743,9620|
7291,1164|
6670,2148|
5103,2462|
7516,9114|
1973,953|
4842,3878|
905,2558|
3493,2550|
7699,5170|
794,4030|
2019,2705|
6127,2799|
2713,3409|
1905,92|
7910,8205|
2418,3647|
8979,6647|
5629,6632|
2134,6754|
648,6469|
5411,609|
1225,9735|
3149,3710|
3952,4861|
968,5472|
8853,1134|
6525,8222|
7032,5466|
4115,8567|
1563,5378|
3332,8088|
7385,946|
2873,1651|
51,480|
970,1068|
1828,7886|
9207,1822|
9765,3917|
4508,3054|
4013,8737|
4672,378|
2468,1752|
744,1539|
4569,2245|
8833,6739|
1162,7893|
6956,5912|
5515,9188|
309,5414|
2140,9586|
2172,2214|
1384,1697|
8721,6716|
3543,4446|
282,196|
8548,9741|
6777,3931|
9881,1306|
2630,40|
3894,5869|
5243,4885|
6765,3624|
5254,2463|
7059,2650|
3551,7889|
4992,3833|
2495,9751|
2666,6713|
2377,1771|
1647,3886|
6308,9147|
1572,7523|
2253,9139|
1415,6580|
883,2554|
7671,4078|
4726,2723|
2029,7746|
7360,7448|
9154,3286|
583,7611|
8987,7196|
1849,9986|
5584,6257|
2785,4901|
8126,6876|
2682,2349|
9917,2662|
4112,2985|
4388,9441|
7114,8152|
1051,6218|
5822,8908|
3993,2120|
8771,5686|
2191,8706|
649,2662|
58,429|
8543,8925|
3109,1553|
4437,6566|
372,2717|
4039,7964|
9577,653|
4370,9190|
1946,4683|
6878,6698|
317,9400|
7714,9128|
8700,1696|
9307,4567|
1378,8809|
7922,4110|
3162,1956|
7537,4977|
3512,1517|
196,2554|
8960,8176|
4007,2531|
2274,9696|
6299,5853|
8950,3845|
9315,5079|
3847,5279|
3185,9652|
6137,9465|
657,233|
1513,270|
3889,2891|
7806,4367|
5189,9636|
9183,9983|
7830,8403|
1351,6454|
1244,8668|
5430,2757|
5366,9307|
4116,5286|
3854,9313|
845,5503|
5990,2608|
3863,1023|
1604,4395|
5322,4253|
5084,1974|
413,6408|
5671,9249|
4659,6946|
5443,8322|
1947,3613|
5209,1948|
2301,9011|
7784,1624|
1327,8741|
6086,1341|
9932,6396|
7188,609|
1946,8893|
6441,8111|
2151,823|
617,5935|
2123,9981|
9990,8661|
7355,8783|
8785,5453|
4383,7251|
4512,9053|
6977,4275|
6747,9170|
514,2184|
1040,3312|
342,5957|
6262,1063|
616,9235|
6192,6448|
3356,1297|
9471,6779|
4926,7291|
4450,6474|
2283,7894|
5908,6024|
8279,1336|
8376,5121|
1495,2532|
7562,4600|
2692,5435|
734,1618|
4440,6145|
9356,1660|
6131,1392|
519,6459|
1876,2851|
3452,2564|
3279,9563|
5435,5689|
4445,9565|
5839,4412|
3221,1484|
7127,828|
2650,251|
364,5100|
8078,854|
8942,2013|
9047,7595|
8067,398|
1933,8770|
8724,1603|
6600,6358|
5829,1425|
350,5152|
3819,1956|
1675,93|
1068,1606|
3197,5948|
122,4346|
6272,4596|
3219,249|
4192,3437|
1981,241|
5550,8779|
3617,1742|
3672,2634|
967,3186|
2618,6472|
6860,9769|
3102,2645|
3934,6630|
8588,1649|
3656,70|
9208,8432|
2951,4033|
537,6785|
3119,903|
6603,6559|
6413,996|
84,6782|
3920,9454|
7041,4605|
1022,7940|
789,6418|
7708,4860|
6346,8854|
9961,6438|
5041,8619|
7232,7784|
8495,2596|
5434,5231|
1250,5449|
3362,5550|
5459,9803|
6343,3736|
6239,1708|
6830,4923|
525,9961|
3956,2551|
324,1899|
8040,1569|
3698,1122|
3604,598|
2211,6946|
1494,2388|
5705,5231|
8404,2299|
9842,8517|
2565,9488|
755,5720|
7128,1625|
1344,6904|
6128,2584|
683,1617|
965,1931|
7586,490|
1657,4934|
6597,349|
9289,8277|
415,3436|
682,3218|
7492,9241|
4894,3927|
3721,1687|
6114,492|
6621,2661|
9577,7225|
3419,9121|
8868,2018|
4888,4504|
2351,1659|
2006,7305|
7881,5279|
1842,2713|
3259,2155|
891,7701|
4283,945|
8615,811|
4471,2526|
9139,4198|
3132,3881|
1089,8741|
6,1702|
2161,6790|
6755,2442|
6,10000|
7346,2514|
1013,405|
7609,2036|
1114,2360|
6150,9573|
1375,3079|
4125,980|
7667,1253|
2667,9151|
6994,3537|
923,7961|
3523,8757|
4751,4665|
1398,7462|
4671,5768|
5005,9985|
6386,1924|
9056,8895|
2859,7931|
3954,5367|
8741,2212|
9857,7230|
4961,1541|
881,322|
8906,2067|
5844,4461|
8593,5830|
1098,817|
1762,4606|
4585,3269|
7863,3142|
7442,74|
3550,9101|
9755,2358|
7324,5555|
3397,7388|
7413,3282|
3348,1561|
2933,8464|
2469,9600|
1684,6996|
7075,9248|
4242,1907|
7038,6916|
8304,5552|
2324,8825|
2483,8136|
5330,9951|
3143,2359|
159,8002|
1311,4451|
7400,3189|
1800,9146|
7614,7989|
6045,5690|
4642,5132|
3856,1717|
2519,2743|
8521,5504|
7101,3568|
1734,2777|
3725,831|
2299,6078|
3984,9632|
5774,8282|
3972,719|
4855,6816|
951,1033|
6104,2346|
7819,8182|
1965,7803|
8908,1558|
4696,1573|
9302,8461|
96,158|
1237,6026|
8181,1253|
8625,5740|
1462,7164|
1694,907|
1484,5270|
8255,9031|
3471,2091|
4923,942|
3452,981|
4673,5608|
3741,3747|
4976,9698|
5333,87|
8651,7975|
3711,9918|
4590,8858|
1775,1210|
9042,2033|
3071,6705|
9407,7552|
892,3804|
1944,6919|
2,3922|
1798,5478|
444,5118|
611,1388|
8823,1987|
5137,9294|
3500,703|
1729,3277|
2236,7189|
3342,7232|
6661,4946|
599,2519|
258,2235|
2652,8202|
9194,185|
53,8423|
1031,249|
4593,5163|
493,6106|
5464,6364|
8026,6518|
5379,7163|
922,2058|
108,6191|
1188,1311|
611,6877|
7925,5160|
136,8312|
9712,9251|
5661,6577|
3516,7825|
4853,5743|
9954,117|
8508,4397|
2637,3188|
5972,4694|
7937,3099|
4904,9255|
6659,6671|
3438,9963|
3632,1406|
2104,8952|
3965,2473|
4253,9553|
5618,6089|
2507,4076|
1834,3301|
2154,4523|
7648,5043|
3118,5320|
4777,1226|
7148,2375|
5836,3147|
2096,6724|
5192,4437|
8734,9868|
2090,3104|
8014,4643|
2347,1600|
9675,7692|
2928,993|
6476,4763|
3651,6019|
2929,2578|
9208,1095|
4241,7970|
5737,9597|
810,1367|
8542,7551|
8695,1640|
4198,8586|
67,4478|
8438,862|
242,1667|
3560,879|
4698,2243|
6895,1389|
8127,3168|
885,9972|
8888,3127|
827,1273|
2266,7387|
7538,9811|
11,1658|
2088,9022|
2745,537|
4263,4159|
4106,2773|
1052,2214|
8075,8483|
1170,5218|
8611,5090|
8985,1713|
7751,2344|
7737,1003|
390,7846|
2969,3299|
5564,81|
9398,5236|
3016,7179|
3995,786|
6666,2390|
9258,7517|
6941,8282|
1267,143|
3244,2961|
7083,2416|
2070,7224|
3999,2|
386,9816|
5792,6494|
8627,8408|
8762,1111|
361,7891|
3650,605|
1150,3374|
2106,2723|
9341,700|
1393,3326|
7489,1097|
4578,7290|
8858,3339|
2579,4787|
3989,2822|
795,4307|
2357,8605|
3312,7669|
4967,5336|
2974,8544|
8353,1333|
5276,2368|
2122,8679|
9909,1288|
8797,9188|
2322,564|
7169,4698|
5171,7927|
8464,2888|
6650,3927|
1758,1056|
6824,1874|
8057,961|
6486,7595|
5782,291|
3263,4573|
5064,5587|
2177,5997|
5974,3552|
3656,1842|
6213,8565|
3523,342|
1907,1065|
1781,7522|
3966,7418|
5703,1517|
4156,5389|
806,9128|
4821,1054|
2332,8176|
8362,1122|
5153,2069|
485,4665|
8666,5763|
5082,177|
2557,7712|
768,2819|
8151,5000|
1906,795|
5067,8017|
8161,8165|
1534,7852|
2868,1769|
5967,2166|
2062,5729|
5326,8946|
6929,5112|
9291,6586|
398,1665|
5341,2439|
2077,3991|
6773,8698|
1194,1848|
5030,4012|
1657,4505|
8776,3164|
9043,8450|
1718,5174|
9710,1920|
6954,799|
1478,6955|
6817,2453|
9464,6506|
9700,8447|
961,8995|
3766,4662|
4268,9589|
4249,8594|
8086,1345|
1729,2942|
4824,3541|
3726,1657|
2590,9080|
9979,2729|
2530,5627|
2632,1804|
1961,6176|
8895,907|
705,4474|
6728,1380|
1591,8756|
1561,2486|
6154,5340|
4467,7929|
5999,4885|
1015,8566|
2292,2714|
1170,272|
1155,7082|
1558,2984|
8566,4949|
6711,4169|
5512,8291|
4149,3985|
6954,3722|
3238,5584|
6039,4786|
4722,7271|
6578,9954|
2768,7833|
7404,479|
4752,4247|
6523,5392|
839,2933|
5522,1208|
7003,935|
2896,9052|
511,680|
9479,7601|
1554,3904|
7701,2137|
351,3584|
589,6034|
5399,4235|
487,613|
9084,2899|
881,8877|
9217,1735|
7853,4756|
1387,9542|
8250,7413|
1846,8788|
328,4345|
3366,1868|
5844,1182|
3970,5671|
3142,2087|
1947,6051|
2297,6516|
8646,6671|
2313,1625|
3337,6110|
7236,1180|
2658,2870|
1762,8132|
6822,2196|
2939,549|
1306,6679|
4549,2454|
1299,3210|
5165,4207|
975,6726|
6620,8|
5159,7368|
1785,7327|
9010,2633|
3936,9733|
7563,1071|
4503,2651|
1384,3387|
2331,6623|
8043,6310|
3298,7323|
3038,2580|
4447,1472|
2498,157|
8565,7842|
700,3477|
2454,3996|
9917,5343|
2722,2126|
117,8458|
6969,7714|
3887,6693|
3385,3149|
8200,2666|
9033,534|
2534,4652|
9610,5887|
3144,3852|
2636,7934|
5978,4284|
1755,7882|
8142,8231|
2629,1478|
1209,8837|
9140,1236|
9294,188|
735,2436|
702,8574|
9625,8038|
5921,8413|
6277,1235|
3803,3321|
7121,9477|
4741,4734|
7008,83|
7859,2422|
553,4031|
727,309|
6160,176|
4194,4684|
8233,4889|
60,1419|
5628,2469|
4091,868|
472,2677|
6654,37|
1927,1455|
796,534|
1230,1111|
2532,6564|
9514,31|
2546,4304|
2204,7399|
107,7350|
9195,1289|
4269,6444|
6844,467|
6979,7260|
2281,940|
8376,526|
1990,2686|
1530,945|
4037,1207|
1986,7957|
318,27|
4084,8091|
8570,7414|
5447,6789|
6292,7778|
7474,5420|
4522,3086|
3625,4334|
2950,9212|
2171,8787|
7769,5386|
2225,1082|
5428,9777|
7456,606|
2837,598|
5053,1984|
1388,2089|
2963,1596|
512,1033|
549,7421|
2890,8603|
2410,6209|
6832,8928|
9050,1160|
3897,8949|
1137,6474|
3004,3454|
8866,7861|
9342,3812|
475,1532|
548,2674|
5011,8264|
9728,3224|
7410,6882|
2733,2840|
9634,3850|
2532,9181|
1026,7536|
9187,7287|
6827,1769|
4032,3570|
3659,3656|
1673,8951|
4714,8621|
1333,7113|
1339,8678|
6462,2688|
6817,63|
9944,7215|
3470,794|
2360,847|
7504,8501|
6974,8734|
7333,2490|
2193,1851|
1507,774|
3729,8818|
9707,8803|
7726,2982|
9475,5021|
4467,6230|
5257,8331|
5811,8499|
662,6684|
6322,9055|
5037,1976|
6541,245|
501,2706|
3345,8744|
1466,4305|
1603,9956|
8845,5034|
2189,9988|
5666,3028|
5642,2511|
769,47|
440,815|
631,6501|
5352,5943|
3963,305|
547,5432|
5069,167|
8950,6337|
9170,2234|
5688,2992|
2187,6070|
9973,5734|
5820,9072|
5455,2560|
3981,4169|
9284,5229|
1209,2504|
7682,6023|
3987,1102|
8098,5689|
7859,9814|
221,7161|
3410,7021|
9550,8952|
8283,6530|
5624,7861|
295,2562|
8650,786|
8575,849|
5300,3818|
5034,8190|
9013,5097|
4753,1001|
9410,3103|
5955,5244|
2426,1700|
9263,2036|
5619,4016|
759,5419|
2740,6513|
537,6604|
4178,1463|
8932,5547|
8357,711|
2120,1957|
3511,1674|
2540,6889|
5896,170|
8799,2377|
3990,620|
1339,2579|
2449,2438|
347,8119|
4743,13|
6538,2555|
1344,8979|
9624,2919|
6907,2244|
6720,348|
2068,2568|
5665,477|
5179,1888|
5656,2912|
2204,8146|
9242,1433|
6736,2540|
2397,2221|
8749,3870|
6912,1219|
8382,5470|
1685,6413|
273,2563|
700,6952|
4892,2340|
7196,2461|
1831,8567|
133,9958|
8313,8786|
6934,7220|
6945,101|
3950,1192|
8677,9807|
1569,5899|
5527,3266|
5474,4827|
3019,1220|
2662,1646|
9716,4547|
2959,7437|
9005,1504|
5878,8683|
3753,5884|
2408,2297|
8496,2198|
6196,6179|
8802,4042|
3810,9594|
4059,574|
4125,9042|
2811,6890|
2812,3567|
3435,799|
9278,9943|
5544,5097|
284,680|
9462,2356|
8104,5768|
3492,2127|
2953,8302|
7461,8135|
7369,7373|
2361,263|
6352,2813|
8487,7943|
5419,7248|
2317,5091|
2022,418|
1374,6149|];